package org.lql.algo.codecrush.hot100.dynamicProgramming;

/**
 * @author: liangqinglong
 * @date: 2025-09-13 20:26
 * @description: 322. 零钱兑换 <a href="https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class CoinChange {

	public int coinChange(int[] coins, int amount) {
		int[] dp = new int[amount + 1];
		for (int i = 1; i <= amount; i++) {
			dp[i] = Integer.MAX_VALUE;
			for (int coin : coins) {
				if (i - coin >= 0) {
					dp[i] = Math.min(dp[i], dp[i - coin] + 1);
				}
			}
		}
		return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
	}

	public static void main(String[] args) {
		int[] coins = new int[]{1, 2, 5};
		int amount = 11;
		CoinChange coinChange = new CoinChange();
		System.out.println(coinChange.coinChange(coins, amount));
	}
}
